package club.vann.nowcoder;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>难度：Medium</p>
 * <p>题目：最长递增子序列</p>
 * <p>描述：给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
 * 示例1
 * 输入
 * 复制
 * [2,1,5,3,6,4,8,9,7]
 * 返回值
 * 复制
 * [1,3,4,8,9]
 * 示例2
 * 输入
 * 复制
 * [1,2,8,6,4]
 * 返回值
 * 复制
 * [1,2,4]
 * 说明
 * 其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）
 * 备注:
 * n \leq 10^5n≤10
 * 5
 *
 * 1 \leq arr_i \leq 10^91≤arr
 * i
 * ​
 *  ≤10
 * 9</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-22:14:44:23
 */
public class NC91 {
    public static void main(String[] args) {
        NC91 nc91 = new NC91();

        System.out.println("Result["+Arrays.toString(TestCase.ANS)+"] : " + Arrays.toString(nc91.LIS(TestCase.ARR)));
        System.out.println("Result["+Arrays.toString(TestCase.ANS1)+"] : " + Arrays.toString(nc91.LIS(TestCase.ARR1)));
    }

    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
        // 动态规划
        int n = arr.length;
        if(n == 0) {
        }
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i ++) {
            dp[i] = 1;
            for(int j = 0; j < i; j ++) {
                if(arr[j] <= arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        return null;
    }

    static class TestCase {
        public static int[] ANS = {1,3,4,8,9};
        public static int[] ARR = {2,1,5,3,6,4,8,9,7};

        public static int[] ANS1 = {1,2,4};
        public static int[] ARR1 = {1,2,8,6,4};
    }
}
